package com.leetcode.q367;

import java.util.HashSet;
import java.util.Set;

/**
 * <p> description: desc</p>
 *
 * @author tanzc
 * @date 2022/3/30
 **/
public class IsPerfectSquare {
    /**
     * 暴力遍历计算
     *
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        int i = 1;
        while (i * i < num) {
            i++;
        }
        if (i * i == num) {
            return true;
        } else {
            return false;
        }
    }

    static Set<Integer> squareSet = new HashSet<>();
    static Integer maxInteger = 2147483647;

    /**
     * 发现使用暴力破解，当num较大时，前面有很多遍历都是无效遍历
     * 考虑如何避免这些无效遍历
     * 二分法？每次取中间的数求平方，来缩减遍历范围
     *
     * @param num
     * @return
     */
    public boolean isPerfectSquare2(int num) {
        if (squareSet.contains(num)) {
            return true;
        }

        int left = 0, right = 46340, middle = (left + right) / 2;
        long square;
        while (left <= right) {
            square = (long) middle * middle;
            if (square < maxInteger) {
                squareSet.add((int) square);
            }
            if (square < num) {
                left = middle + 1;
            } else if (square > num) {
                right = middle - 1;
            } else {
                return true;
            }
            middle = (left + right) / 2;
        }
        return false;

    }

    public boolean isPerfectSquare3(int num) {
        if (squareSet.contains(num)) {
            return true;
        }

        int square = 0;
        for (int i = 1; square < num; i += 2) {
            square += i;
            squareSet.add(square);
        }
        if (square == num) {
            return true;
        } else {
            return false;
        }
    }
}
